package com.rui.study.algorithm.P_正则表达式匹配;

import java.util.Arrays;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-09 09:39
 **/
public class Solution2回溯法_状态表 {

    private String s;

    private String p;

    private int m,n;

    private boolean matched;

    private int[][] state;

    private long count;

    /**
     * '.' 匹配任意单个字符。
     * '*' 匹配零个或多个前面的元素。
     *
     * 输入:
     * s = "aab"
     * p = "c*a*b"
     * 输出: true
     *
     * 输入:
     * s = "mississippi"
     * p = "mis*is*p*."
     * 输出: false
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        this.s = s;
        this.p = p;
        this.m = s.length();
        this.n = p.length();
        this.state = new int[m][n];
        this.matched = false;
        matches(0, 0);
        return this.matched;
//        return s.matches(p);
    }


    private void matches(int i, int j) {
        count++;
        if (i == m || j == n) {
            if (i == m && j == n)
                this.matched = true;
            if (j+1 < n && p.charAt(j+1) == '*') {
                matches(i, j+2);    // *排除异己(*=0)
            }
            return;
        }

        if (state[i][j] != 1) {
            state[i][j] = 1;
        } else {
            return;
        }

        // 有*
        if (j+1 < n && p.charAt(j+1) == '*') {
            if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                matches(i+1, j);    // *贪婪碰撞(*=n)
                matches(i+1, j+2);  // *适可而止(*=1)
            }
            matches(i, j+2);    // *排除异己(*=0)
        } else {
            if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                matches(i+1, j+1);
            }
        }
    }


    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        Solution2回溯法_状态表 solution1回溯法 = new Solution2回溯法_状态表();
//        boolean result = solution1回溯法.isMatch("a", "ab*");
        boolean result = solution1回溯法.isMatch("aab", "c*a*b");
//        boolean result = solution1回溯法.isMatch("mississippi", "mis*is*p*.");
//        boolean result = solution1回溯法.isMatch("abaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaababaabaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbabababaaaaabababbabbbabababbababbbabababababaaabababaabababababababaabbbababbababababaabbbabab", ".*a*b*a*b*a*b*a*b*a*b*a*b*");
        long end = System.currentTimeMillis();
        for (int i = 0; i < solution1回溯法.m; i++) {
            System.out.println(Arrays.toString(solution1回溯法.state[i]));
        }
        System.out.println("是否匹配：" + result + ", 耗时：[" + (end - begin) + "ms], 递归次数: [" + solution1回溯法.count + "]");
    }
}
